#define _CRT_SECURE_NO_WARNINGS

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<list>
using namespace std;



 struct ListNode {
    int val;
    struct ListNode* next;
    
};

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL)
        return list2;
    if (list2 == NULL)
        return list1;
    ListNode* newhead;
    ListNode* newtail;
    newhead = newtail = NULL;
    while (list1 && list2)
    {
        if (list1->val <= list2->val)
        {
            if (newhead == NULL)
            {
                newhead = newtail = list1;
                list1 = list1->next;
            }
            else
            {
                newtail->next = list1;
                newtail = newtail->next;
                list1 = list1->next;
            }
        }
        else
        {
            if (newhead == NULL)
            {
                newhead = newtail = list2;
                list2 = list2->next;
            }
            else
            {
                newtail->next = list2;
                newtail = newtail->next;
                list2 = list2->next;
            }
        }
    }
    if (list1)
    {
        newtail->next = list1;
    }
    else
    {
        newtail->next = list2;
    }
    return newhead;
}

void ListNodeInit(ListNode** pphead)
{
    *pphead = new ListNode;
}

//int main12()
//{
//    ListNode* l1 ;
//    ListNode* l2 ;
//    ListNodeIit(&l1);
//     ListNodeIit(&l2);
//
//    l1->val = 1;
//    l2->val = 1;
//    ListNode * a ,*b ,*c,*d,*e ;
//    ListNodeIit(&a);
//    ListNodeIit(&b);
//    ListNodeIit(&c);
//    ListNodeIit(&d);
//    ListNodeIit(&e);
//    a->val = 2;
//    b->val = 3;
//    c->val = 4;
//
//    l1->next = b;
//    b->next = c;
//    c->next = NULL;
//    l2->next = a;
//    d->val = 4;
//    a->next = d;
//    d->next = NULL;
//    ListNode* ret=mergeTwoLists(l1, l2);
//
//    return 0;
//}


void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    while (m > 0 && n > 0)
    {
        if (*(nums1 + m - 1) > *(nums2 + n - 1))
        {
            *(nums1 + m + n - 1) = *(nums1 + m - 1);
            m--;
        }
        else
        {
            *(nums1 + m + n - 1) = *(nums2 + n - 1);
            n--;
        }
    }
    while (n > 0)
    {
        if (n > 0)
        {
            *(nums1 + n - 1) = *(nums2 + n - 1);
            n--;
        }
    }

}

int removeElement(int* nums, int numsSize, int val) {
    int src = 0;
    int dst = 0;
    while (src < numsSize)
    {
        if (nums[src] == val)
        {
            src++;
        }
        else
        {
            nums[dst] = nums[src];
            src++;
            dst++;
        }
    }
    return dst;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL)
        return head;
    ListNode* p1 = NULL;
    ListNode* p2 = head;
    ListNode* p3 = head->next;
    while (p2)
    {
        p2->next = p1;
        p1 = p2;
        p2 = p3;
        if (p2)
            p3 = p3->next;
    }
    return p1;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    ListNode* newTail;
    ListNode* newHead;
    ListNode* pcur = head;
    newHead = newTail = NULL;
    while (pcur)
    {

        if (pcur->val != val)
        {
            if (newHead == NULL)
            {
                newHead = newTail = pcur;
            }
            else
            {
                newTail->next = pcur;
                newTail = newTail->next;
            }
        }
        pcur = pcur->next;
    }
    if (newTail)
    {
        newTail->next = NULL;
    }
    return newHead;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    ListNode* pcur;
    ListNode* prve;
    pcur = prve = head;
    while (prve && prve->next)
    {
        pcur = pcur->next;
        prve = prve->next->next;
    }
    return pcur;
}

int maximumCount(int* nums, int numsSize) {
    int count1 = 0;
    int count2 = 0;
    for (int i = 0; i < numsSize; i++)
    {
        if (nums[i] < 0)
            count1++;
        else if (nums[i] == 0)
            continue;
        else
            count2++;
    }
    return count1 > count2 ? count1 : count2;
}

struct ListNode* deleteDuplicates(struct ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;
    else
    {
        ListNode* prve = head->next;
        ListNode* pcur = prve->next;
        while (pcur)
        {
            if (prve->val == pcur->val)
            {
                prve->next = pcur->next;
                prve = pcur->next;
                free(pcur);
                pcur = prve->next;
            }
            else
            {
                prve = prve->next;
                pcur = pcur->next;
            }
        }
    }
    return head;
}

//int main()
//{
//    ListNode* ls = NULL;
//    ListNodeInit(&ls);
//    ListNode* a;
//    ListNodeInit(&a);
//    ListNode* b;
//    ListNodeInit(&b);
//    ListNode* c;
//    ListNodeInit(&c);
//    ls->next = a;
//    a->next = b;
//    b->next = c;
//    c->next = NULL;
//    a->val = 1;
//    b->val = 1;
//    c->val = 2;
//    ListNode* ret=deleteDuplicates(ls);
//}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode* head) {
    if (head == NULL || head->next == NULL)
    {
        return false;
    }
    else
    {
        ListNode* fast = head->next;;
        ListNode* slow = head;
        while (slow != fast)
        {
            if (fast == NULL || fast->next == NULL)
            {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }

}

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    ListNode* pA = headA;
    ListNode* pB = headB;
    while (pA != pB)
    {
        if (!pA)
        {
            pA = headB;
        }
        else
        {
            pA = pA->next;
        }
        if (!pB)
        {
            pB = headA;
        }
        else
        {
            pB = pB->next;
        }
    }
    return pA;
}

//int main()
//{
//    ListNode* l1;
//    ListNode* l2;
//    ListNodeInit(&l1);
//    ListNodeInit(&l2);
//    ListNode* a;
//    ListNode* b;
//    ListNode* c;
//    ListNode* d;
//    ListNode* e;
//    ListNodeInit(&e);
//    ListNodeInit(&d);
//    ListNodeInit(&c);
//    ListNodeInit(&b);
//    ListNodeInit(&a);
//    l1->next = a;
//    a->next = b;
//    b->next = c;
//    c->next = NULL;
//    l2->next = d;
//    d->next = e;
//    e->next = NULL;
//    a->val = 2;
//    b->val = 6;
//    c->val = 4;
//    d->val = 1;
//    e->val = 5;
//    getIntersectionNode(l1, l2);
//    return 0;
//}



bool isPalindrome(struct ListNode* head) {
    if (head->next == NULL)
        return true;
    else if (head->next->next == NULL)
    {
        if (head->val == head->next->val)
            return true;
        else
            return false;
    }
    else
    {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        if (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next;
        }
        if (slow->next->next == NULL && fast)
        {
            if (slow->next->val == head->val)
                return true;
            else
                return false;
        }
        else
        {
            ListNode* p1 = slow;
            ListNode* p2 = p1->next;
            ListNode* p3 = p2->next;
            while (p2)
            {
                p2->next = p1;
                p1 = p2;
                p2 = p3;
                if (p3)
                    p3 = p3->next;
            }
            ListNode* left = head;
            ListNode* right = p1;
            while (left != slow)
            {
                if (left->val != right->val)
                    return false;
                left = left->next;
                right = right->next;
            }
            return true;
        }
    }
}

int getDecimalValue(struct ListNode* head) {
    int n = 0;
    ListNode* cur = head;
    while (cur)
    {
        if (cur->val == 1)
        {
            n <<= 1;
            n |= 1;
            cur = cur->next;
        }
        else
        {
            n <<= 1;
            cur = cur->next;
        }
    }
    return n;
}

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    ListNode* pa = headA;
    ListNode* pb = headB;
    while (pa != pb)
    {
        pa = pa == NULL ? headB : pa->next;
        pb = pb == NULL ? headA : pb->next;
    }
    return pa;
}

int main()
{
    ListNode* l1;
    ListNode* l2;
    ListNodeInit(&l1);
    ListNodeInit(&l2);
    ListNode* a;
    ListNode* b;
    ListNode* c;
    ListNode* d;
    ListNode* e;
    ListNodeInit(&e);
    ListNodeInit(&d);
    ListNodeInit(&c);
    ListNodeInit(&b);
    ListNodeInit(&a);
    l1 = a;
    a->next = b;
    b->next = c;
    c->next = d;
    d->next = NULL;
    e->next= NULL;
    a->val = 1;
    b->val = 2;
    c->val = 2;
    d->val = 1;
    e->val = 1;
    isPalindrome(l1);
    return 0;
}